#include <iostream>
#include <stdlib.h>
#include "myhead.h"
#include <stack>
using namespace std;

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T)
{
    char c;
    scanf("%c", &c);
    if (c == ' ')
        T = NULL;
    else
    {
        if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
            exit(OVERFLOW);
        T->data = int(c - '0');
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

Status PrintBiTNode(BiTNode *node)
{
    cout << node->data << " ";
    return OK;
}
Status PreOrderTraverse(BiTree T, Status (*CallBack)(BiTNode *T))
{
    if (T)
    {
        if (CallBack(T))
            if (PreOrderTraverse(T->lchild, CallBack))
                if (PreOrderTraverse(T->rchild, CallBack))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}

Status InOrderTraverse(BiTree T, Status (*CallBack)(BiTNode *T))
{
    if (T)
    {
        if (InOrderTraverse(T->lchild, CallBack))
            if (CallBack(T))
                if (InOrderTraverse(T->rchild, CallBack))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}

Status PostOrderTraverse(BiTree T, Status (*CallBack)(BiTNode *T))
{
    if (T)
    {
        if (PostOrderTraverse(T->lchild, CallBack))
            if (PostOrderTraverse(T->rchild, CallBack))
                if (CallBack(T))
                    return OK;
        return ERROR;
    }
    else
        return OK;
}
// TODO 非递归中序遍历二叉树
// 指针q为根♂,
// 栈tmp为空
// while (1)
// {
//     if (q不为null){
//         q入栈
//         q等于q的左子树
//     }
//     else{
//         if (栈为空)
//             return
//         else{
//             q = 出栈元素
//             执行回调函数
//             q = q的右子树
//             }
//      }
// }

Status InOrderTraverse2(BiTree T, Status (*CallBack)(BiTNode *T))
{
    BiTree q = T;
    stack<BiTNode *> tmpStack;
    while (1)
    {
        if (q)
        {
            tmpStack.push(q);
            q = q->lchild;
        }
        else
        {
            if (tmpStack.empty())
                return OK;
            else
            {
                q = tmpStack.top();
                tmpStack.pop();
                CallBack(q);
                q = q->rchild;
            }
        }
    }
}